package linkedlist.leetcode_19;

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preNode = new ListNode(-1);
        preNode.next = head;
        ListNode fast = preNode;
        ListNode slow = preNode;

        //快指针先走n步
        while (n != 0){
            fast = fast.next;
            n--;
        }
        //要删除倒数第n个节点，就要找到第n个节点的前一个。
        //两个指针一起走，当fast.next = null时，慢指针停到第n个节点的前一个节点位置。
        while (fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        //删除第n个节点
        slow.next = slow.next.next;

        //head有可能是被删除节点，使用哑节点的好处。
        return preNode.next;
    }
}
